/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-11-07
 * Time: 0:13
 */

//面试题 17.19. 消失的两个数字
public class Demo {
    public int[] missingTwo(int[] nums) {
        //1.把所有的数异或在一起，包括1到N下标
        int tmp = 0;
        for(int x : nums) tmp ^= x;
        for(int i = 1; i <= nums.length+2; i++) tmp ^= i;

        //找出a和b比特位不同的哪一位，方便后续分开异或找出a,b
        int diff = 0;
        while(true){
            if(((tmp>>diff) & 1) == 1)
                break;
            else diff++;
        }

        int[] ret = new int[2];


        //将所有的数按照diff不同分两类异或
        for(int x : nums){
            if(((x>>diff) & 1) == 1) ret[0] ^= x;
            else ret[1] ^= x;
        }

        for(int i = 1; i <= nums.length+2; i++)
            if(((i>>diff) & 1) == 1) ret[0] ^= i;
            else ret[1] ^= i;

        return ret;
    }
}
